package swap

/*
Quick
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
*/

type quick struct {
}

// 哨兵劃分 左子数组、基准数、右子数组，且满足“左子数组任意元素≤基准数≤右子数组任意元素”
func (q quick) partition(nums []int, left, right int) int {
	// 以 nums[left] 为基准数
	i, j := left, right
	for i < j {
		for i < j && nums[j] >= nums[left] {
			j-- // 从右向左找首个小于基准数的元素
		}
		for i < j && nums[i] <= nums[left] {
			i++ // 从左向右找首个大于基准数的元素
		}
		// 元素交换
		nums[i], nums[j] = nums[j], nums[i]
	}
	// 當i == j 的時候
	// 将基准数交换至两子数组的分界线
	nums[i], nums[left] = nums[left], nums[i]
	return i
}

func (q quick) quickSort(nums []int, left, right int) {
	// 子数组长度为 1 时终止递归
	if left >= right {
		return
	}
	// 哨兵划分
	pivot := q.partition(nums, left, right)
	// 递归左子数组、右子数组
	q.quickSort(nums, left, pivot-1)
	q.quickSort(nums, pivot+1, right)
}

// 優化
// 我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选
// 元素的中位数作为基准数。
func (q quick) medianThree(nums []int, left, mid, right int) int {
	l, m, r := nums[left], nums[mid], nums[right]
	if (l <= m && m <= r) || (r <= m && m <= l) {
		return mid //m在l和r之间
	}
	if (m <= l && l <= r) || (r <= l && l <= m) {
		return left //l在m和r之间
	}
	return right
}

/*哨兵划分（三数取中值）*/
func (q quick) partitionUp(nums []int, left, right int) int {
	//以nums[left]为基准数
	med := q.medianThree(nums, left, (left+right)/2, right)
	//将中位数交换至数组最左端
	nums[left], nums[med] = nums[med], nums[left]
	//以nums[left]为基准数
	i, j := left, right
	for i < j {
		for i < j && nums[j] >= nums[left] {
			j-- //从右向左找首个小于基准数的元素
		}
		for i < j && nums[i] <= nums[left] {
			i++ //从左向右找首个大于基准数的元素
		}
		//元素交换
		nums[i], nums[j] = nums[j], nums[i]
	}
	//将基准数交换至两子数组的分界线
	nums[i], nums[left] = nums[left], nums[i]
	return i //返回基准数的索引
}
func (q quick) quickSortUp(nums []int, left, right int) {
	// 子数组长度为 1 时终止递归
	if left >= right {
		return
	}
	// 哨兵划分
	pivot := q.partitionUp(nums, left, right)
	// 递归左子数组、右子数组
	q.quickSort(nums, left, pivot-1)
	q.quickSort(nums, pivot+1, right)
}

// 優化遞歸算法
func (q quick) quickSortRecursion(nums []int, left, right int) {
	// 子数组长度为 1 时终止
	for left < right {
		// 哨兵划分操作
		pivot := q.partitionUp(nums, left, right)
		// 对两个子数组中较短的那个执行快速排序
		if pivot-left < right-pivot {
			q.quickSort(nums, left, pivot-1) // 递归排序左子数组
			left = pivot + 1
		} else {
			q.quickSort(nums, pivot+1, right) // 递归排序右子数组
			right = pivot - 1
			// 剩余未排序区间为 [left, pivot- 1]
		}
	}
}
